package com.sjc.algorithm.list;

/**
 * @author by SangJiacun
 * @Date 2020/5/10 11:49
 */
public class MyList {

    private Node head;
    private Node last;
    private int size;

    public static void main(String[] args) {
        //插入元素
        MyList myList = new MyList();
        myList.saveList(23,0);
        myList.saveList(65,0);
        myList.saveList(29,1);
        myList.saveList(11,2);
        myList.saveList(74,4);
        myList.printList();

        //查找元素
        Node nodeByIndex = myList.findNodeByIndex(3);
        System.out.println(nodeByIndex.data);

        //删除元素
        myList.removeByIndex(0);
        myList.removeByIndex(1);
        myList.removeByIndex(myList.size-1);
        myList.printList();
    }

    /**
     * 向链表的指定位置插入元素
     * @param data 数据
     * @param index 指定位置
     */
    public void saveList(int data, int index){
        if(index <0 || index > size){
            throw new IndexOutOfBoundsException("链表新插入的位置 超过了链表的实际大小!");
        }

        // 插入的节点
        Node newNode = new Node(data);
        if(size == 0){
            //空链表
            head = newNode;
            last = newNode;
        }else if(index == 0){
            // 如果在 链表头 插入节点
            newNode.next = head;
            head = newNode;
        }else if(index == size){
            //如果在 链表末尾 插入节点
            last.next = newNode;
             last = newNode;
        }else{
            //插入中间
            Node preNode = findNodeByIndex(index - 1);
            newNode.next =  preNode.next;
            preNode.next = newNode;
        }
        size++;
    }

    /**
     * 返回指定位置的数据
     * @param index
     * @return
     */
    public Node findNodeByIndex(int index){
        if(index <0 || index > size){
            throw new IndexOutOfBoundsException(" 超过了链表实际的范围!");
        }
        Node temp = head;
        for(int i=0; i< index;i++){
            temp = temp.next;
        }
        return temp;
    }

    public Node removeByIndex(int index){
        if(index <0 || index >= size){
            throw new IndexOutOfBoundsException(" 超过了链表实际的范围!");
        }
        Node removeNode = null;
        if(0 ==index){
            // 删除头结点
            removeNode = head;
            head = head.next;
        }else if(size == index){
            // 删除尾节点
            Node prevnode = findNodeByIndex(index - 1);
            removeNode = prevnode.next;
            prevnode.next = null;
            last = prevnode;
        }else{
            //删除中间节点
            Node prevnode = findNodeByIndex(index - 1);
            removeNode = prevnode.next;
            prevnode.next = prevnode.next.next;
        }
        size--;
        return removeNode;
    }

    /**
     * 打印链表数据
     */
    public void printList(){
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");

        Node temp = head;
        while(null != temp.next){
            sb.append(temp.data+" ");
            temp = temp.next;
        }
        sb.append(temp.data+" ]");
        System.out.println(sb.toString());
    }

    public static class Node {
        int data;
        Node next;

        Node(int data){
            this.data = data;
        }
    }

}
